#!/usr/bin/env python
#-*- coding: utf-8 -*-

from itertools import permutations

## KemenyYoung helper function
#  @param   a,b Candidates
#  @param   P   A list of preference orderings of candidates (one for each voter)
#  @returns The number of voters ranking candidate b above candidate a
def S(a, b, P):
    return len([p for p in P if p.index(a) < p.index(b)])

## KemenyYoung helper function
#  @param   p   A preference ordering of candidates
#  @param   P   A list of preference orderings of candidates (one for each voter)
#  @returns A measure for how well p represents the preferences in P
def Sp(p, P):
    res = 0
    for j in range(len(p)-1):
        for k in range(j+1, len(p)):
            res += S(p[j], p[k], P)
    return res    

## Nicer output for a precedence ordering
#  @param   p   A preference ordering
def prettyprint_preference(p):
    print " < ".join([c for c in p]), "--> Winner:", p[-1]

## Implements the Kemeny-Young election method
#  @param   P   A list of preference orderings (one for each voter)
#  @returns A preference function (out of P) that is the Kemeny-Young winner
def KemenyYoung(P):
    c = list(permutations(P[0]))
    scores = [Sp(p, P) for p in c]
    scoresmax = max(scores)
    if scores.count(scoresmax) > 1:
        print "Ambiguous. Optimal results are:"
        for i in range(len(c)):
            if scores[i] == scoresmax:
                prettyprint_preference(c[i])
    else:
        print "The optimal function is:"
        prettyprint_preference(P[scores.index(scoresmax)])



if __name__ == '__main__':

    print ""
    print "(Example 86 from the lecture)"
    ## expected result: possible winners b and d
    P = ['dcba'] * 3 \
      + ['cbad'] * 2 \
      + ['acbd'] * 2 \
      + ['adbc'] * 2
    KemenyYoung(P)

    print ""
    print "(Exercise 9.1)"
    P = ['badec'] * 25 \
      + ['edcba'] * 12 \
      + ['ceabd'] * 11 \
      + ['dabec'] * 14 \
      + ['ebdca'] * 18 \
      + ['cdaeb'] * 10 \
      + ['cdeba'] * 10
    KemenyYoung(P)
